package datastructure.tree;

/**
 * 顺序存储二叉树
 *
 * 通过数组模拟二叉树的结构
 *      实现前序遍历和中序遍历
 *
 */
public class ArrayBinaryTree {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        // 创建一个 ArrBinaryTree
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);

        // 前序遍历 1,2,4,5,3,6,7
//        arrBinaryTree.preOrder();

        // 中序遍历 1,2,4,5,3,6,7
        arrBinaryTree.infixOrder();
    }

    /**
     * 编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历
     */
    static class ArrBinaryTree {
        /**
         * 存储数据结点的数组
         */
        private final int[] arr;

        /**
         * 构造函数
         *
         * @param arr 数组对象
         */
        public ArrBinaryTree(int[] arr) {
            this.arr = arr;
        }

        /**
         * 重载preOrder
         */
        public void preOrder() {
            this.preOrder(0);
        }

        /**
         * 重载infixOrder
         */
        public void infixOrder() {
            this.infixOrder(0);
        }

        /**
         * 前序遍历
         *
         * @param index 数组的下标
         */
        public void preOrder(int index) {
            // 如果数组为空，或者 arr.length = 0
            // 这边不是递归中止的条件
            if (arr == null || arr.length == 0) {
                System.out.println("数组为空，不能按照二叉树的前序遍历");
            }
            // 输出当前这个元素
            System.out.println(arr[index]);

            // 向左递归遍历
            // 递归中止的条件是数组长度不越界
            if ((index * 2 + 1) < arr.length) {
                preOrder(2 * index + 1);
            }
            // 向右递归遍历
            if ((index * 2 + 2) < arr.length) {
                preOrder(2 * index + 2);
            }
        }

        /**
         * 中序遍历
         *
         * @param index 数组的下标
         */
        public void infixOrder(int index) {
            //如果数组为空，或者 arr.length = 0
            if (arr == null || arr.length == 0) {
                System.out.println("数组为空，不能按照二叉树的前序遍历");
            }
            //向左递归遍历
            if ((index * 2 + 1) < arr.length) {
                infixOrder(2 * index + 1);
            }

            //输出当前这个元素
            System.out.println(arr[index]);

            //向右递归遍历
            if ((index * 2 + 2) < arr.length) {
                infixOrder(2 * index + 2);
            }
        }

    }

}

